package com.example.demo.myMap.impl;


import com.example.demo.myMap.MyMap;

import java.util.ArrayList;
import java.util.List;

/**
 * @Auther: zwg
 * @Date: 2018/9/5 14:12
 * @Description:
 */
public class MyHashMap<K,V> implements MyMap<K,V> {

    //数组的默认初始长度
    private static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    //扩容阈值
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    private int defaultInitSize;
    private float defaultLoadFactor;

    //Map当中entry数量
    private int entryUseSize;

    //数组
    private Entry<K,V>[] table = null;

    public MyHashMap(){
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

    public MyHashMap(int defaultInitSize, float defaultLoadFactor) {
        if (defaultInitSize < 0) {
            throw new IllegalArgumentException("Illegal initial capacity: " + defaultInitSize);
        }
        if(defaultLoadFactor<=0){
            throw new IllegalArgumentException("Illegal load factor: " + defaultLoadFactor);
        }

        this.defaultInitSize = defaultInitSize;
        this.defaultLoadFactor = defaultLoadFactor;

        table = new Entry[this.defaultInitSize];

    }

    @Override
    public V put(K key, V value) {
        //是否需要扩容
        //扩容后肯定需要散列
        if(entryUseSize>= defaultInitSize*defaultLoadFactor){
            resize(defaultInitSize * 2);
        }
        int index = hash(key) & (defaultInitSize - 1);
        if(table[index]==null){
            //如果位置没有被占用，则直接放值
            table[index] = new Entry<K,V>(key,value,null);
            ++entryUseSize;
        }else{
            Entry<K, V> e = table[index];
            if(key == e.getKey()||key.equals(e.getKey())){
                e.setValue(value);
            }else {
                table[index] = new Entry<>(key, value, e);
                ++entryUseSize;
            }
        }
        return value;
    }

    public int hash(K key){
        //通过hash算法得到key的hashCode值来定位key在entry数组中的位置
        int hashCode = key.hashCode();
        hashCode ^= (hashCode >>> 20) ^ (hashCode >>> 12);
        return hashCode ^ (hashCode >>> 7) ^ (hashCode >>> 4);
    }

    private void resize(int i) {
        Entry[] newTable = new Entry[i];
        defaultInitSize = i;
        entryUseSize = 0;
        rehash(newTable);
    }

    private void rehash(Entry[] newTable) {
        //得到原来老的Entry集合
        List<Entry<K, V>> entryList = new ArrayList<Entry<K, V>>();
        for(Entry<K,V> entry : table){
            if(entry!=null){
                entryList.add(entry);
            }
        }

        //覆盖旧的引用
        if (newTable.length > 0) {
            table = newTable;
        }
        //重新put到新的entry数组
     for(Entry<K,V> entry: entryList){
         recursionEntry(entry);
     }
    }

    //递归拿到相同hash(key)的数据
    public void recursionEntry(Entry<K,V> entry){
        if(entry!=null) {
            put(entry.getKey(), entry.getValue());
            Entry<K, V> e = entry.getNext();
            if(e!=null) {
                put(e.getKey(), e.getValue());
                recursionEntry(e.getNext());
            }
        }
    }

    @Override
    public V get(K key) {
        int index = hash(key)&(defaultInitSize-1);
        if(table[index]==null){
            return null;
        }else{
            Entry<K, V> entry = table[index];
            if(entry!=null) {
                if(key == entry.getKey() || key.equals(entry.getKey())) {
                    return entry.getValue();
                }else if(entry.getNext()!=null) {
                  return  getNextEntry(key, entry.getNext());
                }
            }
        }
        return null;
    }

    //递归拿相同hash(key)的数据
    public V getNextEntry(K key,Entry<K, V> entry){
        if(key == entry.getKey() || key.equals(entry.getKey())){
           return entry.getValue();
        }else{
            if(entry.getNext()!=null) {
               return getNextEntry(key, entry.getNext());
            }
        }
        return null;
    }
}
